# 20. 有效的括号
# 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
#
# 有效字符串需满足：
#
# 左括号必须用相同类型的右括号闭合。
# 左括号必须以正确的顺序闭合。
#
#
# 示例 1：
#
# 输入：s = "()"
# 输出：true
# 示例 2：
#
# 输入：s = "()[]{}"
# 输出：true
# 示例 3：
#
# 输入：s = "(]"
# 输出：false
# 示例 4：
#
# 输入：s = "([)]"
# 输出：false
# 示例 5：
#
# 输入：s = "{[]}"
# 输出：true
#
#
# 提示：
#
# 1 <= s.length <= 104
# s 仅由括号 '()[]{}' 组成
from collections import deque


class Solution:
    io = {
        ']': '[',
        ')': '(',
        '}': '{'
    }

    def isValid(self, s: str) -> bool:
        input_ = s
        stack = deque()
        for each in input_:
            tail = stack[-1] if len(stack) else None
            if each in Solution.io:
                if Solution.io[each] == tail:
                    stack.pop()
                else:
                    stack.append(each)
                    break
            else:
                stack.append(each)
        return len(stack) == 0


solution = Solution()
print(solution.isValid('()[]{}'))
